if output is in C: <module>.h specification of the generated graph module <module>.c body of the generated graph module yy<module>.w macro file defining type specific operations if output is in Modula-2: <module>.md definition module of the generated graph module <module>.mi implementation module of the generated graph module <module>.imp import statements
J. Grosch: "Ast - A Generator for Abstract Syntax Trees", GMD Forschungsstelle an der Universitaet Karlsruhe, Compiler Generation Report No. 15
J. Grosch: "Tool Support for Data Structures", Structured Programming, 12, 31-38 (1991) [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [ [
RULE /* Ast: concrete syntax */
/* parser grammar */
Specification = <
= TreeCodes PropPart DeclPart RulePart Modules .
= 'MODULE' Name TreeCodes PropPart DeclPart RulePart
'END' Name Modules .
> .
TreeCodes = <
= SubUnit .
= 'TREE' SubUnit Codes .
= 'TREE' Name SubUnit Codes .
> .
Codes = <
= .
= Codes 'EXPORT' tTargetCode .
= Codes 'IMPORT' tTargetCode .
= Codes 'GLOBAL' tTargetCode .
= Codes 'LOCAL' tTargetCode .
= Codes 'BEGIN' tTargetCode .
= Codes 'CLOSE' tTargetCode .
> .
SubUnit = <
= .
= SubUnit 'SUBUNIT' Name .
= SubUnit 'VIEW' Name .
> .
PropPart = Props .
Props = <
=
= Props 'PROPERTY' Properties
= Props 'PROPERTY' Properties 'FOR' Names
= Props 'SELECT' Names
> .
DeclPart = <
= .
= 'DECLARE' Decls .
> .
Decls = <
= .
MoreNonterms = Decls Names '=' AttrDecls '.' .
MoreTerminals = Decls Names ':' AttrDecls '.' .
> .
Names = <
= .
= Names Name .
= Names ',' .
> .
RulePart = <
= .
= 'RULE' Types .
> .
Types = <
= .
Nonterminal = Types Name BaseTypes '=' AttrDecls Extensions '.' .
Terminal = Types Name BaseTypes ':' AttrDecls Extensions '.' .
Abstract = Types Name BaseTypes ':=' AttrDecls Extensions '.' .
> .
BaseTypes = <
= .
= '<-' Names .
> .
Extensions = <
= .
= '<' Types '>' .
> .
AttrDecls = <
= .
ChildSelct = AttrDecls Name ':' Name Properties .
ChildNoSelct = AttrDecls Name Properties .
AttrTyped = AttrDecls '[' Name ':' Name Properties ']' .
AttrInteger = AttrDecls '[' Name Properties ']' .
> .
Properties = <
= .
= Properties 'INPUT' .
= Properties 'OUTPUT' .
= Properties 'SYNTHESIZED' .
= Properties 'INHERITED' .
= Properties 'THREAD' .
= Properties 'REVERSE' .
= Properties 'IGNORE' .
= Properties 'VIRTUAL' .
> .
Modules = <
= .
= Modules 'MODULE' Name TreeCodes DeclPart RulePart 'END' Name .
> .
Name = <
= tIdent .
= tString .
> .
/* lexical grammar */
tIdent : <
= Letter .
= tIdent Letter .
= tIdent Digit .
= tIdent '_' .
> .
tString : <
= "'" Characters "'" .
= '"' Characters '"' .
> .
tTargetCode : '{' Characters '}' .
Comment : '/*' Characters '*/' .
Characters : <
= .
= Characters Character .
> .
RULE
Prog = PROGRAM tIdent ';' 'DECLARE' Decls 'BEGIN' Stats 'END' '.' .
Decls = <
Decls1 = Decl .
Decls2 = Decls ';' Decl .
> .
Decl = <
Var = tIdent ':' Type .
Proc0 = PROCEDURE tIdent ';' 'DECLARE' Decls 'BEGIN' Stats 'END' .
Proc = PROCEDURE tIdent '(' Formals ')' ';'
'DECLARE' Decls 'BEGIN' Stats 'END' .
> .
Formals = <
Formals1 = Formal .
Formals2 = Formals ';' Formal .
> .
Formal = <
Value = tIdent ':' Type .
Ref = VAR tIdent ':' Type .
> .
Type = <
Int = INTEGER .
Real = REAL .
Bool = BOOLEAN .
Array = ARRAY '[' Lwb: tIntegerConst '..' Upb: tIntegerConst ']' OF Type .
> .
Stats = <
Stats1 = Stat .
Stats2 = Stats ';' Stat .
> .
Stat = <
Assign = Adr ':=' Expr .
Call0 = tIdent .
Call = tIdent '(' Actuals ')' .
If = IF Expr THEN Then: Stats ELSE Else: Stats 'END' .
While = WHILE Expr DO Stats 'END' .
Read = READ '(' Adr ')' .
Write = WRITE '(' Expr ')' .
> .
Actuals = <
Expr1 = Expr .
Expr2 = Actuals ',' Expr .
> .
Expr = <
Less = Lop: Expr '<' Rop: Expr .
Plus = Lop: Expr '+' Rop: Expr .
Times = Lop: Expr '*' Rop: Expr .
Not = NOT Expr .
'()' = '(' Expr ')' .
IConst = tIntegerConst .
RConst = tRealConst .
False = FALSE .
True = TRUE .
Adr = <
Name = tIdent .
Index = Adr '[' Expr ']' .
> .
> .
tIdent : [Ident: tIdent] .
tIntegerConst : [Integer ] .
tRealConst : [Real : REAL ] .
TREE /* MiniLAX: abstract syntax */
IMPORT { FROM Idents IMPORT tIdent;
TYPE tPosition = RECORD Line, Column: CARDINAL; END; }
GLOBAL { FROM Idents IMPORT tIdent; }
RULE
MiniLax = Proc .
Decls = <
NoDecl = .
Decl = Next: Decls REV [Ident: tIdent] [Pos: tPosition] <
Proc = Formals Decls Stats .
Var = Type .
> .
> .
Formals = <
NoFormal = .
Formal = Next: Formals REV [Ident: tIdent] [Pos: tPosition] Type .
> .
Type = <
Integer = .
Real = .
Boolean = .
Array = Type [Lwb] [Upb] [Pos: tPosition] .
Ref = Type .
> .
Stats = <
NoStat = .
Stat = Next: Stats REV <
Assign = Adr Expr [Pos: tPosition] .
Call = Actuals [Ident: tIdent] [Pos: tPosition] .
If = Expr Then: Stats Else: Stats .
While = Expr Stats .
Read = Adr .
Write = Expr .
> .
> .
Actuals = <
NoActual = [Pos: tPosition] .
Actual = Next: Actuals REV Expr .
> .
Expr = [Pos: tPosition] <
Binary = Lop: Expr Rop: Expr [Operator] .
Unary = Expr [Operator] .
IntConst = [Value ] .
RealConst = [Value: REAL ] .
BoolConst = [Value: BOOLEAN] .
Adr = <
Index = Adr Expr .
Ident = [Ident: tIdent] .
> .
> .
# ifndef yyTREE /* throughout replace TREE by the name of the tree module */
# define yyTREE
<import_declarations>
# define bool char
# define NoTREE (tTREE) NULL
# define k<type_1> 1
# define k<type_1> 2
...
typedef unsigned short TREE_tKind; /* or char */
typedef unsigned short TREE_tMark;
typedef unsigned short TREE_tLabel;
typedef union TREE_Node * tTREE;
typedef void (* TREE_tProcTree) ();
<export_declarations>
# ifndef TREE_NodeHead
# define TREE_NodeHead
# endif
typedef struct { TREE_tKind yyKind; TREE_tMark yyMark; TREE_NodeHead } TREE_tNodeHead;
typedef struct { TREE_tNodeHead yyHead;
<children_and_attributes_of_type_1> } y<type_1>;
typedef struct { TREE_tNodeHead yyHead;
<children_and_attributes_of_type_2> } y<type_2>;
...
union TREE_Node {
TREE_tKind Kind;
TREE_tNodeHead yyHead;
y<type_1> <type_1>;
y<type_2> <type_2>;
...
};
extern tTREE TREERoot;
extern unsigned long TREE_HeapUsed;
extern unsigned short TREE_NodeSize [];
extern char * TREE_NodeName [];
extern tTREE n<type_1> ();
extern tTREE n<type_2> ();
...
extern tTREE m<type_1> (<input_children_and_attributes_of_type_1>);
extern tTREE m<type_2> (<input_children_and_attributes_of_type_2>);
...
extern tTREE MakeTREE (TREE_tKind Kind);
extern bool TREE_IsType (tTREE t, TREE_tKind Kind);
extern void ReleaseTREE (tTREE t);
extern void ReleaseTREEModule ();
extern void WriteTREENode (FILE * f, tTREE t);
extern void WriteTREE (FILE * f, tTREE t);
extern tTREE ReadTREE (FILE * f);
extern void PutTREE (FILE * f, tTREE t);
extern tTREE GetTREE (FILE * f);
extern void TraverseTREETD (tTREE t, void (* Procedure) (tTREE t));
extern void TraverseTREEBU (tTREE t, void (* Procedure) (tTREE t));
extern tTREE ReverseTREE (tTREE t);
extern tTREE CopyTREE (tTREE t);
extern bool CheckTREE (tTREE t);
extern void QueryTREE (tTREE t);
extern bool IsEqualTREE (tTREE t1, tTREE t2);
extern void BeginTREE ();
extern void CloseTREE ();
# endif
DEFINITION MODULE TREE;
IMPORT IO; (* throughout replace TREE by the name of the tree module *)
<import_declarations>
CONST
NoTREE = NIL;
<type_1> = 1;
<type_2> = 2;
...
TYPE
tTREE = POINTER TO yyNode;
tProcTree = PROCEDURE (tTREE);
<export_declarations>
TYPE
yytNodeHead = RECORD yyKind, yyMark: SHORTCARD; END;
TYPE
y<type_1> = RECORD yyHead: yytNodeHead;
<children_and_attributes_of_type_1> END;
y<type_2> = RECORD yyHead: yytNodeHead;
<children_and_attributes_of_type_2> END;
...
yyNode = RECORD
CASE : SHORTCARD OF
| 0 : Kind: SHORTCARD;
| ... : yyHead: yytNodeHead;
| <type_1> : <type_1> : y<type_1>;
| <type_2> : <type_2> : y<type_2>;
...
END;
END;
VAR TREERoot : tTREE;
VAR HeapUsed : LONGCARD;
VAR yyNodeSize: ARRAY [ ... ] OF SHORTCARD;
PROCEDURE n<type_1> (): tTREE;
PROCEDURE n<type_2> (): tTREE;
...
PROCEDURE m<type_1> (<input_children_and_attributes_of_type_1>): tTREE;
PROCEDURE m<type_2> (<input_children_and_attributes_of_type_2>): tTREE;
...
PROCEDURE MakeTREE (Kind: SHORTCARD): tTREE;
PROCEDURE IsType (Tree: tTREE; Kind: SHORTCARD): BOOLEAN;
PROCEDURE ReleaseTREE (Tree: tTREE);
PROCEDURE ReleaseTREEModule;
PROCEDURE WriteTREENode (f: IO.tFile; Tree: tTREE);
PROCEDURE WriteTREE (f: IO.tFile; Tree: tTREE);
PROCEDURE ReadTREE (f: IO.tFile): tTREE;
PROCEDURE PutTREE (f: IO.tFile; Tree: tTREE);
PROCEDURE GetTREE (f: IO.tFile): tTREE;
PROCEDURE ReverseTREE (Tree: tTREE): tTREE;
PROCEDURE TraverseTREETD (Tree: tTREE; Proc: tProcTree);
PROCEDURE TraverseTREEBU (Tree: tTREE; Proc: tProcTree);
PROCEDURE CopyTREE (Tree: tTREE): tTree;
PROCEDURE CheckTREE (Tree: tTREE): BOOLEAN;
PROCEDURE QueryTREE (Tree: tTREE);
PROCEDURE IsEqualTREE (Tree1, Tree2: tTREE): BOOLEAN;
PROCEDURE BeginTREE;
PROCEDURE CloseTREE;
END TREE.
/* int */
# define beginint(a)
# define closeint(a)
# define readint(a) (void) fscanf (yyf, "%d", & a);
# define writeint(a) (void) fprintf (yyf, "%d", a);
# define getint(a) yyGet ((char *) & a, sizeof (a));
# define putint(a) yyPut ((char *) & a, sizeof (a));
# define copyint(a, b)
# define equalint(a, b) a == b
/* short */
# define beginshort(a)
# define closeshort(a)
# define readshort(a) (void) fscanf (yyf, "%hd", & a);
# define writeshort(a) (void) fprintf (yyf, "%hd", a);
# define getshort(a) yyGet ((char *) & a, sizeof (a));
# define putshort(a) yyPut ((char *) & a, sizeof (a));
# define copyshort(a, b)
# define equalshort(a, b) a == b
/* long */
# define beginlong(a)
# define closelong(a)
# define readlong(a) (void) fscanf (yyf, "%ld", & a);
# define writelong(a) (void) fprintf (yyf, "%ld", a);
# define getlong(a) yyGet ((char *) & a, sizeof (a));
# define putlong(a) yyPut ((char *) & a, sizeof (a));
# define copylong(a, b)
# define equallong(a, b) a == b
/* unsigned */
# define beginunsigned(a)
# define closeunsigned(a)
# define readunsigned(a) (void) fscanf (yyf, "%u", & a);
# define writeunsigned(a) (void) fprintf (yyf, "%u", a);
# define getunsigned(a) yyGet ((char *) & a, sizeof (a));
# define putunsigned(a) yyPut ((char *) & a, sizeof (a));
# define copyunsigned(a, b)
# define equalunsigned(a, b) a == b
/* float */
# define beginfloat(a)
# define closefloat(a)
# define readfloat(a) (void) fscanf (yyf, "%g", & a);
# define writefloat(a) (void) fprintf (yyf, "%g", a);
# define getfloat(a) yyGet ((char *) & a, sizeof (a));
# define putfloat(a) yyPut ((char *) & a, sizeof (a));
# define copyfloat(a, b)
# define equalfloat(a, b) a == b
/* double */
# define begindouble(a)
# define closedouble(a)
# define readdouble(a) (void) fscanf (yyf, "%lg", & a);
# define writedouble(a) (void) fprintf (yyf, "%lg", a);
# define getdouble(a) yyGet ((char *) & a, sizeof (a));
# define putdouble(a) yyPut ((char *) & a, sizeof (a));
# define copydouble(a, b)
# define equaldouble(a, b) a == b
/* bool */
# define beginbool(a)
# define closebool(a)
# define readbool(a) a = fgetc (yyf) == 'T';
# define writebool(a) (void) fputc (a ? 'T' : 'F', yyf);
# define getbool(a) yyGet ((char *) & a, sizeof (a));
# define putbool(a) yyPut ((char *) & a, sizeof (a));
# define copybool(a, b)
# define equalbool(a, b) a == b
/* char */
# define beginchar(a)
# define closechar(a)
# define readchar(a) a = fgetc (yyf);
# define writechar(a) (void) fputc (a, yyf);
# define getchar(a) yyGet ((char *) & a, sizeof (a));
# define putchar(a) yyPut ((char *) & a, sizeof (a));
# define copychar(a, b)
# define equalchar(a, b) a == b
/* tString */
# define begintString(a)
# define closetString(a)
# define readtString(a)
# define writetString(a) (void) fputs (a, yyf);
# define gettString(a)
# define puttString(a)
# define copytString(a, b)
# define equaltString(a, b) strcmp (a, b)
/* tStringRef */
# define begintStringRef(a)
# define closetStringRef(a)
# define readtStringRef(a)
# define writetStringRef(a) WriteString (yyf, a);
# define gettStringRef(a)
# define puttStringRef(a)
# define copytStringRef(a, b)
# define equaltStringRef(a, b) a == b
/* tIdent */
# define begintIdent(a)
# define closetIdent(a)
# define readtIdent(a) a = yyReadIdent ();
# define writetIdent(a) WriteIdent (yyf, a);
# define gettIdent(a) yyGetIdent (& a);
# define puttIdent(a) yyPutIdent (a);
# define copytIdent(a, b)
# define equaltIdent(a, b) a == b
/* tSet */
# define begintSet(a)
# define closetSet(a)
# define readtSet(a) ReadSet (yyf, & a);
# define writetSet(a) WriteSet (yyf, & a);
# define gettSet(a)
# define puttSet(a)
# define copytSet(a, b)
# define equaltSet(a, b) IsEqual (& a, & b)
/* tPosition */
# define begintPosition(a)
# define closetPosition(a)
# define readtPosition(a)
# define writetPosition(a) WritePosition (yyf, a);
# define gettPosition(a)
# define puttPosition(a)
# define copytPosition(a, b)
# define equaltPosition(a, b) Compare (a, b) == 0
(* INTEGER *)
# define beginINTEGER(a)
# define closeINTEGER(a)
# define readINTEGER(a) a := IO.ReadI (yyf);
# define writeINTEGER(a) IO.WriteI (yyf, a, 0);
# define getINTEGER(a) yyGet (a);
# define putINTEGER(a) yyPut (a);
# define copyINTEGER(a, b)
# define equalINTEGER(a, b) a = b
(* SHORTINT *)
# define beginSHORTINT(a)
# define closeSHORTINT(a)
# define readSHORTINT(a) a := IO.ReadI (yyf);
# define writeSHORTINT(a) IO.WriteI (yyf, a, 0);
# define getSHORTINT(a) yyGet (a);
# define putSHORTINT(a) yyPut (a);
# define copySHORTINT(a, b)
# define equalSHORTINT(a, b) a = b
(* LONGINT *)
# define beginLONGINT(a)
# define closeLONGINT(a)
# define readLONGINT(a) a := IO.ReadI (yyf);
# define writeLONGINT(a) IO.WriteI (yyf, a, 0);
# define getLONGINT(a) yyGet (a);
# define putLONGINT(a) yyPut (a);
# define copyLONGINT(a, b)
# define equalLONGINT(a, b) a = b
(* CARDINAL *)
# define beginCARDINAL(a)
# define closeCARDINAL(a)
# define readCARDINAL(a) a := IO.ReadI (yyf);
# define writeCARDINAL(a) IO.WriteI (yyf, a, 0);
# define getCARDINAL(a) yyGet (a);
# define putCARDINAL(a) yyPut (a);
# define copyCARDINAL(a, b)
# define equalCARDINAL(a, b) a = b
(* SHORTCARD *)
# define beginSHORTCARD(a)
# define closeSHORTCARD(a)
# define readSHORTCARD(a) a := IO.ReadI (yyf);
# define writeSHORTCARD(a) IO.WriteI (yyf, a, 0);
# define getSHORTCARD(a) yyGet (a);
# define putSHORTCARD(a) yyPut (a);
# define copySHORTCARD(a, b)
# define equalSHORTCARD(a, b) a = b
(* LONGCARD *)
# define beginLONGCARD(a)
# define closeLONGCARD(a)
# define readLONGCARD(a) a := IO.ReadI (yyf);
# define writeLONGCARD(a) IO.WriteI (yyf, a, 0);
# define getLONGCARD(a) yyGet (a);
# define putLONGCARD(a) yyPut (a);
# define copyLONGCARD(a, b)
# define equalLONGCARD(a, b) a = b
(* REAL *)
# define beginREAL(a)
# define closeREAL(a)
# define readREAL(a) a := IO.ReadR (yyf);
# define writeREAL(a) IO.WriteR (yyf, a, 0, 6, 1);
# define getREAL(a) yyGet (a);
# define putREAL(a) yyPut (a);
# define copyREAL(a, b)
# define equalREAL(a, b) a = b
(* LONGREAL *)
# define beginLONGREAL(a)
# define closeLONGREAL(a)
# define readLONGREAL(a) a := IO.ReadR (yyf);
# define writeLONGREAL(a) IO.WriteR (yyf, a, 0, 6, 1);
# define getLONGREAL(a) yyGet (a);
# define putLONGREAL(a) yyPut (a);
# define copyLONGREAL(a, b)
# define equalLONGREAL(a, b) a = b
(* BOOLEAN *)
# define beginBOOLEAN(a)
# define closeBOOLEAN(a)
# define readBOOLEAN(a) a := IO.ReadB (yyf);
# define writeBOOLEAN(a) IO.WriteB (yyf, a);
# define getBOOLEAN(a) yyGet (a);
# define putBOOLEAN(a) yyPut (a);
# define copyBOOLEAN(a, b)
# define equalBOOLEAN(a, b) a = b
(* CHAR *)
# define beginCHAR(a)
# define closeCHAR(a)
# define readCHAR(a) a := IO.ReadC (yyf);
# define writeCHAR(a) IO.WriteC (yyf, a);
# define getCHAR(a) yyGet (a);
# define putCHAR(a) yyPut (a);
# define copyCHAR(a, b)
# define equalCHAR(a, b) a = b
(* BITSET *)
# define beginBITSET(a)
# define closeBITSET(a)
# define readBITSET(a) yyReadHex (a);
# define writeBITSET(a) yyWriteHex (a);
# define getBITSET(a) yyGet (a);
# define putBITSET(a) yyPut (a);
# define copyBITSET(a, b)
# define equalBITSET(a, b) a = b
(* BYTE *)
# define beginBYTE(a)
# define closeBYTE(a)
# define readBYTE(a) yyReadHex (a);
# define writeBYTE(a) yyWriteHex (a);
# define getBYTE(a) yyGet (a);
# define putBYTE(a) yyPut (a);
# define copyBYTE(a, b)
# define equalBYTE(a, b) a = b
(* WORD *)
# define beginWORD(a)
# define closeWORD(a)
# define readWORD(a) yyReadHex (a);
# define writeWORD(a) yyWriteHex (a);
# define getWORD(a) yyGet (a);
# define putWORD(a) yyPut (a);
# define copyWORD(a, b)
# define equalWORD(a, b) a = b
(* ADDRESS *)
# define beginADDRESS(a)
# define closeADDRESS(a)
# define readADDRESS(a) yyReadHex (a);
# define writeADDRESS(a) yyWriteHex (a);
# define getADDRESS(a) yyGet (a);
# define putADDRESS(a) yyPut (a);
# define copyADDRESS(a, b)
# define equalADDRESS(a, b) a = b
(* tString *)
# define begintString(a)
# define closetString(a)
# define readtString(a) Strings.ReadL (yyf, a);
# define writetString(a) Strings.WriteL (yyf, a);
# define gettString(a) yyGet (a);
# define puttString(a) yyPut (a);
# define copytString(a, b)
# define equaltString(a, b) Strings.IsEqual (a, b)
(* tStringRef *)
# define begintStringRef(a)
# define closetStringRef(a)
# define readtStringRef(a)
# define writetStringRef(a) StringMem.WriteString (yyf, a);
# define gettStringRef(a)
# define puttStringRef(a)
# define copytStringRef(a, b)
# define equaltStringRef(a, b) a = b
(* tIdent *)
# define begintIdent(a)
# define closetIdent(a)
# define readtIdent(a) a := yyReadIdent ();
# define writetIdent(a) Idents.WriteIdent (yyf, a);
# define gettIdent(a) yyGetIdent (a);
# define puttIdent(a) yyPutIdent (a);
# define copytIdent(a, b)
# define equaltIdent(a, b) a = b
(* tText *)
# define begintText(a)
# define closetText(a)
# define readtText(a)
# define writetText(a) Texts.WriteText (yyf, a);
# define gettText(a)
# define puttText(a)
# define copytText(a, b)
# define equaltText(a, b) FALSE
(* tSet *)
# define begintSet(a)
# define closetSet(a)
# define readtSet(a) Sets.ReadSet (yyf, a);
# define writetSet(a) Sets.WriteSet (yyf, a);
# define gettSet(a)
# define puttSet(a)
# define copytSet(a, b)
# define equaltSet(a, b) Sets.IsEqual (a, b)
(* tRelation *)
# define begintRelation(a)
# define closetRelation(a)
# define readtRelation(a) Relations.ReadRelation (yyf, a);
# define writetRelation(a) Relations.WriteRelation (yyf, a);
# define gettRelation(a)
# define puttRelation(a)
# define copytRelation(a, b)
# define equaltRelation(a, b) Relations.IsEqual (a, b)
(* tPosition *)
# define begintPosition(a)
# define closetPosition(a)
# define readtPosition(a)
# define writetPosition(a) Positions.WritePosition (yyf, a);
# define gettPosition(a)
# define puttPosition(a)
# define copytPosition(a, b)
# define equaltPosition(a, b) Positions.Compare (a, b) = 0